Everything about Big Oh Notation totally explained
In
computational complexity theory,
big O notation is often used to describe how the size of the input data affects an
algorithm's usage of
computational resources (usually running time or memory). It is also called
Big Oh notation,
Landau notation,
Bachmann-Landau notation, and
asymptotic notation. Big O notation is also used in many other scientific and mathematical fields to provide similar estimations.
The symbol
O is used to describe an
asymptotic upper bound for the
magnitude of a function in terms of another, usually simpler, function. There are also other symbols
o, Ω, ω, and
Θ for various other upper, lower, and tight bounds.
Informally, the
O notation is commonly employed to describe an asymptotic tight bound, but tight bounds are more formally and precisely denoted by the
Θ (capital
theta) symbol as described below. This distinction between upper and tight bounds is useful, and sometimes critical; most computer scientists would urge distinguishing the usage of
O and
Θ. In some other fields, however, the
Θ notation isn't commonly known.
Usage
Big O notation has two main areas of application: in
mathematics, it's usually used to characterize the residual term of a truncated
infinite series, especially an
asymptotic series; in
computer science, it's useful in the
analysis of the
complexity of
algorithms.
The notation was first introduced by number theorist
Paul Bachmann in 1894, in the second volume of his book
Analytische Zahlentheorie ("analytic
number theory"), the first volume of which (not yet containing big O notation) was published in 1892. The notation was popularized in the work of another German number theorist
Edmund Landau, hence it's sometimes called a Landau symbol. The big-O, standing for "order of", was originally a capital
omicron; today the identical-looking Latin capital letter
O is also used, but never the digit
zero.
There are two formally close, but noticeably different, usages of this notation:
infinite asymptotics and
infinitesimal asymptotics. This distinction is only in application and not in principle, however—the formal definition for the "big O" is the same for both cases, only with different limits for the function argument.
Equals or member-of and other notational anomalies
In a way to be made precise below,
O(
f(
x)) denotes the collection of functions
g(
x) – viewed as a function of variable
x – that exhibit a growth that's limited to that of
f(
x) in some respect. The traditional notation for stating that
g(
x) belongs to this collection is:
»
This use of the
equals sign is an
abuse of notation, as the above statement isn't an
equation. It is improper to conclude from
g(
x) =
O(
f(
x)) and
h(
x) =
O(
f(
x)) that
g(
x) and
h(
x) are equal. One way to think of this is to consider "=
O" one symbol here. To avoid the anomalous use, some authors prefer to write instead:
»
without difference in meaning.
The common arithmetic operations are often extended to the class concept. For example,
h(
x) +
O(
f(
x)) denotes the collection of functions having the growth of
h(
x) plus a part whose growth is limited to that of
f(
x). Thus,
»
expresses the same as
»
Another anomaly of the notation, although less exceptional, is that it doesn't make explicit which variable is the function argument, which may need to be inferred from the context if several variables are involved. The following two right-hand side big O notations have dramatically different meanings:
»
The first case states that
f(
m) exhibits polynomial growth, while the second, assuming
m > 1, states that
g(
n) exhibits exponential growth. So as to avoid all possible confusion, some authors use the notation
»
meaning the same as what is denoted by others as
»
A final anomaly is that the notation doesn't make clear "where" the function growth is to be considered; infinitesimally near some point, or in the neighbourhood of infinity. This is in contrast with the usual notation for
limits. Similar terminological and notational devices as for limits would resolve both this and the preceding anomaly, but are not in use.
Infinite asymptotics
Big O notation is useful when
analyzing algorithms for efficiency. For example, the time (or the number of steps) it takes to complete a problem of size
n might be found to be
T(
n) = 4
n² − 2
n + 2.
As
n grows large, the
n²
term will come to dominate, so that all other terms can be neglected — for instance when
n = 500, the term 4
n² is 1000 times as large as the 2
n term. Ignoring the latter would have negligible effect on the expression's value for most purposes.
Further, the
coefficients become irrelevant as well if we compare to any other order of expression, such as an expression containing a term n³ or n². Even if
T(
n) = 1,000,000
n², if
U(
n) =
n³, the latter will always exceed the former once
n grows larger than 1,000,000 (
T(1,000,000) = 1,000,000³ =
U(1,000,000)).
So the big O notation captures what remains: we write any of
»
(read as "big o of n squared") and say that the algorithm has
order of n² time complexity.
Infinitesimal asymptotics
Big O can also be used to describe the error term in an approximation
to a mathematical function. For example,
»
(for example
).
Graph theory
It is often useful to bound the running time of
graph algorithms. Unlike most other computational problems, for a graph
G = (
V,
E) there are two relevant parameters describing the size of the input: the number |
V| of vertices in the graph and the number |
E| of edges in the graph. Inside
asymptotic notation (and only there), it's common to use the symbols
V and
E, when someone really means |
V| and |
E|. We adopt this convention here to simplify asymptotic functions and make them easily readable. The symbols
V and
E are never used inside asymptotic notation with their literal meaning, so this abuse of notation doesn't risk ambiguity. For example
means
for a suitable metric of graphs. Another common convention—referring to the values |
V| and |
E| by the names
n and
m, respectively—sidesteps this ambiguity.
Generalizations and related usages
The generalization to functions taking values in any
normed vector space is straightforward (replacing absolute values by norms), where
f and
g need not take their values in the same space. A generalization to functions
g taking values in any
topological group is also possible.
The "limiting process"
x→xo can also be generalized by introducing an arbitrary
filter base, for example to directed
nets
f and
g.
The
o notation can be used to define
derivatives and
differentiability in quite general spaces, and also (asymptotical) equivalence of functions,
»
which is an
equivalence relation and a more restrictive notion than the relationship "
f is
Θ(
g)" from above. (It reduces to
if
f and
g are positive real valued functions.) For example, 2
x is
Θ(
x), but 2
x −
x isn't
o(
x).
Further Information
Get more info on 'Big Oh Notation'.
|
External Link Exchanges
Do you know how hard it is to get a link from a large encyclopaedia? Well we're different and will prove it. To get a link from us just add the following HTML to your site on a relevant page:
<a href="http://big_o_notation.totallyexplained.com">Big O notation Totally Explained</a>
Then simply click through this link from your web page. Our crawlers will verify your link, extract the title of your web page and instantly add a link back to it. If you like you can remove the words Totally Explained and embed the link in article text.
As long as your link remains in place, we'll keep our link to you right here. Please play fair - our crawlers are watching. Your site must be closely related to this one's topic. Any kind of spamming, dubious practises or removing the link will result in your link from us being dropped and, potentially, your whole site being banned. |
